package 堆;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Leedcode373查找和最小的K对数字 {
    public static void main(String[] args) {
        Leedcode373查找和最小的K对数字 o = new Leedcode373查找和最小的K对数字();
        int[] nums1 = {1,1,7};
        int[] nums2 = {2,2,2};
        List<List<Integer>> lists = o.kSmallestPairs(nums1, nums2, 10);
        System.out.println(lists);
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //r如果k小于数组1长度*数组2长度，将数组元素遍历全部添加到结果集中
        List<List<Integer>> lists = new ArrayList<>();

        //创建优先级队列,并将优先级队列修改成大顶堆模式，JDK默认的为小顶堆
        Queue<Number> queue = new PriorityQueue<>((o1, o2) -> (o2.v+o2.u)-(o1.v+o1.u));

        for(int i = 0;i < Math.min(k,nums1.length);i++){

            for(int j = 0; j < Math.min(k,nums2.length);j++){
                if(queue.size() < k){
                    queue.offer(new Number( nums1[i] , nums2[j] ));
                }else{
                    int temp = queue.peek().v + queue.peek().u;
                    if(temp > (nums1[i] + nums2[j])){
                        queue.poll();
                        queue.offer(new Number( nums1[i] , nums2[j] ));
                    }
                }
            }
        }
        //走到这里说明优先级队列里面已经存放了最小的元素
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            Number poll = queue.poll();
            list.add(poll.v);
            list.add(poll.u);
            lists.add(list);
        }
        return lists;
    }
}

class Number {
    int v;
    int u;
    public Number(int v, int u){
        this.v = v;
        this.u = u;
    }
}
